package com.hardy.leecode;

import com.hardy.leecode.model.TreeNode;

import java.util.HashMap;

/**
 * Author: Hardy
 * Date:   2020/11/4
 * Description:
 **/
public class QueOffer07 {

    public static void main(String[] args) {

        int[] a = {1, 2, 3};
        int[] b = {3, 2, 1};

        System.out.println(new Solution().buildTree(a, b));
        a = new int[10];
    }

    static class Solution {

        int[] preorder;
        HashMap<Integer, Integer> dic = new HashMap<>();

        public TreeNode buildTree(int[] preorder, int[] inorder) {
            this.preorder = preorder;
            for (int i = 0; i < inorder.length; i++) dic.put(inorder[i], i);

            return build(0, 0, inorder.length - 1);
        }

        // root: 当前树根 inl: 当前树在中序左边，inr: 当前树在中序左边
        public TreeNode build(int root, int inl, int inr) {
            if (inl > inr) return null;

            int i = dic.get(preorder[root]);                             // 根节点在中序中的位置
            TreeNode node = new TreeNode(preorder[root]);

            node.left = build(root + 1, inl, i - 1);            // 根节点索引 + 1
            node.right = build(i - inl + root + 1, i + 1, inr); // 根节点索引 + 左子树长度 + 1
            return node;
        }
    }
}
